//package Test;
//
//import java.util.*;
//import java.util.HashMap;
//import java.util.Map;
//
//public class Trst01 {

//    //和为是的两个数
//    public int[] twoSum(int[] nums, int target) {
//        int left = 0;
//        //下面别忘了-1,注意取值范围
//        int right = nums.length -1 ;
//        while(left < right){
//            if(nums[left] + nums[right] > target){
//                right--;
//            }else if(nums[left] + nums[right] == target){
//                return new int[]{nums[left],nums[right]};
//            }else{
//                left++;
//            }
//        }
//        //下面两种都可以,为了照顾系统,没有什么用哈,返回数组就可以,它的值没要求,
//        //因为只是为了照顾编译器
//        // return new int[0];
//        return new int[]{0};
//    //最小覆盖子串
////    public static String minWindow(String s,String t){
////        char[] ss = s.toCharArray();
////        char[] tt = t.toCharArray();
////        //通过数组模拟哈希表比哈希表要快
////        int[] map1 = new int[130];
////        //统计有效字符种类
////        int kinds = 0;
////        for(char ch : tt)
////            if(map1[ch] ++ == 0) kinds++;
////        int min = Integer.MAX_VALUE;
////        int start = -1;
////        int[] map2 = new int[130];
////        for(int l = 0,r = 0,count = 0;r < ss.length;r++){
////            //进窗口
////            char in = ss[r];
////            if(++map2[in] == map1[in]) count++;
////            //下面必须写循环,不能写if
////            while(count == kinds){
////                if(r - l + 1< min){
////                    min = r - l + 1;
////                    start = l;
////                }
////                char out = ss[l++];
////                if(map2[out]-- == map1[out]) count--;
////            }
////        }
////        if(start == -1) return new String();
////        else return s.substring(start, start + min);
////    }
//
//    //求子集
////     ArrayList<List<Integer>> ret = new ArrayList<>();
////    List<Integer> path = new ArrayList<>();
////    int n2 = 0;
////    public List<List<Integer>> subsets(int[] nums) {
////        int n = nums.length;
////        n2 = n;
////        dfs(nums,0);
////        return ret;
////    }
////    static void dfs(int[] nums,int pos){
////        //把空集添加进去
////        ret.add(new ArrayList<>(path));
////        for(int i = pos;i<n2;i++){
////            path.add(nums[i]);
////            dfs(nums,i+1);
////            path.remove(path.size()-1);
////        }
////    }
//    public int longestPalindromeSubseq(String s)
//    {
//        // 1. 创建 dp 表
//        // 2. 初始化
//        // 3. 填表
//        // 4. 返回结果
//        int n = s.length();
//        int[][] dp = new int[n][n];
//        for(int i = n - 1; i >= 0; i--)
//        {
//            dp[i][i] = 1;
//            for(int j = i + 1; j < n; j++)
//                if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
//                else dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
//        }
//        return dp[0][n - 1];
//    }
//    public int minCut(String s)
//    {
//        // 1. 预处理
//        int n = s.length();
//        boolean[][] isPal = new boolean[n][n];
//        for(int i = n - 1; i >= 0; i--)
//            for(int j = i; j < n; j++)
//                if(s.charAt(i) == s.charAt(j))
//                    isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
//
//        int[] dp = new int[n];
//        for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
//        for(int i = 0; i < n; i++)
//        {
//            if(isPal[0][i]) dp[i] = 0;
//            else
//            {
//                for(int j = 1; j <= i; j++)
//                    if(isPal[j][i])
//                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
//            }
//        }
//        return dp[n - 1];
//    }
//    public boolean checkPartitioning(String s)
//    {
//        // 1. 利⽤ dp 处理⼀下所有的⼦串是否回⽂
//        int n = s.length();
//        boolean[][] dp = new boolean[n][n];
//        for(int i = n - 1; i >= 0; i--)
//            for(int j = i; j < n; j++)
//                if(s.charAt(i) == s.charAt(j))
//                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//
//        // 2. 枚举第⼆个字符串所有的起始位置和终⽌位置
//        for(int i = 1; i < n - 1; i++)
//            for(int j = i; j < n - 1; j++)
//                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
//                    return true;
//        return false;
//    }
//    public String longestPalindrome(String s)
//    {
//        // 1. 创建 dp 表
//        // 2. 初始化
//        // 3. 填表
//        // 4. 返回值
//        int n = s.length();
//        boolean[][] dp = new boolean[n][n];
//        int begin = 0, len = 1; // 标记⼀下最⻓⼦串的起始位置和⻓度
//        for(int i = n - 1; i >= 0; i--)
//        {
//            for(int j = i; j < n; j++)
//            {
//                if(s.charAt(i) == s.charAt(j))
//                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//                if(dp[i][j] && j - i + 1 > len)
//                {
//                    len = j - i + 1;
//                    begin = i;
//                }
//            }
//        }
//        return s.substring(begin, begin + len);
//    }
//    public int countSubstrings(String s)
//    {
//        // 1. 创建 dp 表
//        // 2. 初始化
//        // 3. 填表
//        // 4. 返回值
//        int n = s.length();
//        boolean[][] dp = new boolean[n][n];
//        int ret = 0;
//        for(int i = n - 1; i >= 0; i--)
//        {
//            for(int j = i; j < n; j++)
//            {
//                if(s.charAt(i) == s.charAt(j))
//                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//                if(dp[i][j])
//                    ret++;
//            }
//        }
//        return ret;
//    }
////    public int numberOfArithmeticSlices(int[] nums)
////    {
////        // 优化
////        Map<Long, List<Integer>> hash = new HashMap<>();
////        int n = nums.length;
////        for(int i = 0; i < n; i++)
////        {
////            long tmp = (long)nums[i];
////            if(!hash.containsKey(tmp))
////                hash.put(tmp, new ArrayList<Integer>());
////            hash.get(tmp).add(i);
////        }
////        int[][] dp = new int[n][n];
////        int sum = 0;
////        for(int j = 2; j < n; j++) // 固定倒数第⼀个数
////            for(int i = 1; i < j; i++) // 枚举倒数第⼆个数
////            {
////                long a = 2L * nums[i] - nums[j];
////                if(hash.containsKey(a))
////                {
////                    for(int k : hash.get(a))
////                        if(k < i) dp[i][j] += dp[k][i] + 1;
////                        else break; // ⼩优化
////                }
////
////                 sum += dp[i][j];
////                 }
////         return sum;
////         }
//    public int longestArithSeqLength(int[] nums)
// {
//         // 优化
//         Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
//         hash.put(nums[0], 0);
//
//         // 建表
//         int n = nums.length;
//        int[][] dp = new int[n][n];
//        for(int i = 0; i < n; i++) // 初始化
//            Arrays.fill(dp[i], 2);
//
//        int ret = 2;
//        for(int i = 1; i < n; i++) // 固定倒数第⼆个数
//        {
//            for(int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
//            {
//                int a = 2 * nums[i] - nums[j];
//                if(hash.containsKey(a))
//                {
//                    dp[i][j] = dp[hash.get(a)][i] + 1;
//                    ret = Math.max(ret, dp[i][j]);
//                }
//            }
//            hash.put(nums[i], i);
//        }
//        return ret;
//    }
//    public int lenLongestFibSubseq(int[] arr)
//    {
//        // 优化：将 数组中的元素 + 下标 绑定在⼀起，扔到哈希表中
//        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
//        int n = arr.length;
//        for(int i = 0; i < n; i++) hash.put(arr[i], i);
//        int[][] dp = new int[n][n];
//        for(int i = 0; i < n; i++)
//            for(int j = 0; j < n; j++)
//                dp[i][j] = 2;
//
//        int ret = 2;
//        for(int j = 2; j < n; j++) // 固定最后⼀个数
//            for(int i = 1; i < j; i++) // 枚举倒数第⼆个数
//            {
//                int a = arr[j] - arr[i];
//                if(a < arr[i] && hash.containsKey(a))
//                    dp[i][j] = dp[hash.get(a)][i] + 1;
//                ret = Math.max(ret, dp[i][j]);
//            }
//        return ret < 3 ? 0 : ret;
//    }
//    public int longestSubsequence(int[] arr, int difference)
//    {
//        // 创建⼀个哈希表，在哈希表中做 dp
//        Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // arr[i],
//        int ret = 1;
//        for(int a : arr)
//        {
//            hash.put(a, hash.getOrDefault(a - difference, 0) + 1);
//            ret = Math.max(ret, hash.get(a));
//        }
//        return ret;
//    }
//    public int findLongestChain(int[][] pairs)
//    {
//        // 预处理
//        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
//        int n = pairs.length;
//        int[] dp = new int[n]; // 建表
//        for(int i = 0; i < n; i++) dp[i] = 1; // 初始化
//        int ret = 1;
//        for(int i = 1; i < n; i++)
//        {
//            for(int j = 0; j < i; j++)
//                if(pairs[j][1] < pairs[i][0])
//                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//            ret = Math.max(ret, dp[i]);
//        }
//        return ret;
//    }
//    public static void main(String[] args) {
//        String str = " 1 2 3 ";
//        String newS  = str.replace(" ","");
//        System.out.println(str);
//        System.out.println(newS);
//    }
//
//}
